Asynchronous Transfer Mode (ATM) has emerged as the primary networking technology for next-generation digital communications. ATM provides a connection-based, fast packet switching technology that can be used to deliver many different types of information including audio, video, and data in real time.
ATM has a connection oriented protocol that associates each ATM data packet (called a "cell" in ATM terminology) with a given "virtual channel" supported by a physical link. Each connection is identified by two sub-fields: the Virtual Channel Identifier ("VCI") and the Virtual Path Identifier ("VPI"). Together, these fields are used in multiplexing, demultiplexing and switching a cell through the network. The VCI and VPI are not addresses; they are explicitly assigned at each segment (link between ATM switches) of a connection when the connection is established, and they remain for the duration of the connection.
When an ATM switch receives an incoming cell on an input port, it must determine which output port to route the cell to based on the incoming cell's VPI, VCI and input port physical identifier. The ATM switch must also determine new VPI and VCI values to substitute into the cell header so the cell will be correctly routed by the next ATM network segment. The ATM switch typically looks up this connection information in a VP/VC connection table based on the cell header's VPI and VCI information plus additional "physical layer" (PHY) information identifying the input port. To maximize throughput of cells through the ATM switch, it is important to provide a rapid and efficient technique and arrangement for accessing the proper connection information from the connection table.
Under international ATM standards, the virtual path identifier (VPI) and virtual channel identifier (VCI) fields have the following sizes:
the VPI field is twelve bits long; and PA1 the VCI field is sixteen bits long.
A typical size for the physical link identifier (PHY) is 5 bits. Thus, the total length of these three fields together is on the order of thirty-three bits--corresponding to about 8.9 billion (2.sup.33) combinations. However, the maximum number of connections a particular ATM switch can set up is typically restricted to a much lower value (for example, 16K). In the most general case, it should be possible to use any arbitrary sub-set of the total number of 8.9 billion PHY, VPI, VCI combinations as identifiers for the channels that the ATM switch sets up. The problem is to find an efficient mechanism that can take the PHY, VPI, VCI field (e.g., 33 bits long), find out whether it is a valid combination of bits, and output a pointer to one of a smaller (e.g., 16K) connections in a virtual path/virtual channel connection table sized to accommodate the number of connections the ATM switch can maintain.
U.S. Pat. No. 5,414,701 to Shtayer et al provides one approach to solving this problem. The Shtayer et al. patent describes an address compression method that relies on a hierarchical arrangement of separate link, virtual path, and virtual channel tables. In Shtayer et al, the PHY information indexes into a "link" table that provides a virtual path pointer. The virtual path pointer is used in combination with the VPI from the cell header to index into one of many virtual path tables. The virtual path table provides a virtual channel offset that is, in turn, used in combination with the cell header's VCI to index into one of many virtual channel tables. The virtual channel tables provide ingress connection identifiers that are used to physically route data through an ATM system.
While Shtayer et al's approach may avoid the need for a large, mostly unused connection table, its process of using link information to index a link table, using information looked up in the link table to index a virtual path table, etc. is unduly time consuming and inefficient. Furthermore, it may be difficult to maintain Shtayer et al's complex hierarchically structured, separate link, virtual path and virtual channel tables.
U.S. Pat. No. 5,481,687 to Goubert et al. uses masking to form subsets of reduced addresses that may then be translated to provide a non-overlapping series of relative addresses. Goubert's technique requires a complex use of different masks for selecting different address bits, and may suffer from flexibility problems.